package cn.michael.dev.leetcode;

import cn.michael.dev.entity.ListNode;

/**
 * Created by hufenggang on 2021/10/25.
 *
 * 对链表实现插入排序
 *
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 */
public class Problem147 {
    public ListNode insertionSortList(ListNode head) {
        ListNode newListNode = new ListNode(0);
        ListNode pre;
        newListNode.next = head;

        while (head != null && head.next != null) {
            if (head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = newListNode;
            while (pre.next.val < head.next.val) {
                pre = pre.next;
            }
            ListNode curr = head.next;
            head.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
        }
        return newListNode.next;
    }
}
